//
//  300. 最长上升子序列.swift
//  Top600
//
//  Created by rjb on 2021/8/10.
//

import Foundation

// 最长递增子序列
// 最长递增子序列长度

class Solution300 {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        var result = 1
        var dp = Array(repeating: 1, count: nums.count)
        for i in 0..<nums.count {
            for j in 0..<i {
                if nums[i] > nums[j] {
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
            if dp[i] > result {
                result = dp[i]
            }
        }
        return result
    }
    static func test() {
        let solution = Solution300()
        let nums = [10,9,2,5,3,7,101,18]
        let result = solution.lengthOfLIS(nums)
        print(result)
    }
}
